The selection of branching variables is a key component of branch-and-boundalgorithms for solving Mixed-Integer Programming (MIP) problems since thequality of the selection procedure is likely to have a significant effect onthe size of the enumeration tree. State-of-the-art procedures base theselection of variables on their "LP gains", which is the dual bound improvementobtained after branching on a variable. There are various ways of selectingvariables depending on their LP gains. However, all methods are evaluatedempirically. In this paper we present a theoretical model for the selection ofbranching variables. It is based upon an abstraction of MIPs to a simplersetting in which it is possible to analytically evaluate the dual boundimprovement of choosing a given variable. We then discuss how the analyticalresults can be used to choose branching variables for MIPs, and we giveexperimental results that demonstrate the effectiveness of the method on MIPLIB2010 "tree" instances where we achieve a 5% geometric average time and nodeimprovement over the default rule of SCIP, a state-of-the-art MIP solver.
展开▼
